/*题目：编写一个程序，将第二行整数序列使用插入排序（从大到小：降序），将第三行字符
串使用选择排序（按字母表顺序从小到大ABC...Zabc...z：升序）排序，并分行输出！
输入格式：
输入三行，第一行是一个整数 n（不超过 100），第二行分别有 n 个乱序整数数列，第三行
是一串字符串。整数之间用空格隔开。
输出格式：
输出两行，分别将以上两行按照降序和升序排列，其中大写字母放在小写字母前面。
输入样例：
10
19 27 10 8 29 4 36 7 1 100
abytarmvjaAx 
输出样例：
100 36 29 27 19 10 8 7 4 1
Aaaabjmrtvxy
*/
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
void insertion_sort_desc(int arr[], int n);  
void selection_sort_asc(char *str);  
  
int main() {  
    int n;  
    scanf("%d", &n);  
    int *int_arr = (int *)malloc(n * sizeof(int));  
    for (int i = 0; i < n; i++) {  
        scanf("%d", &int_arr[i]);  
    }  
    insertion_sort_desc(int_arr, n);  
  
    char str[1024];
    scanf("%s", str);   
  
    selection_sort_asc(str);  
  
    
    for (int i = 0; i < n; i++) {  
        printf("%d ", int_arr[i]);  
    }  
    printf("\n");  
  
    printf("%s\n", str);  
    free(int_arr);  
  
    return 0;  
}  
  
void insertion_sort_desc(int arr[], int n) {  
    for (int i = 1; i < n; i++) {  
        int key = arr[i];  
        int j = i - 1;  
  
        while (j >= 0 && arr[j] < key) {  
            arr[j + 1] = arr[j];  
            j = j - 1;  
        }  
        arr[j + 1] = key;  
    }  
}  
  
void selection_sort_asc(char *str) {  
    int len = strlen(str);  
    for (int i = 0; i < len - 1; i++) {  
        int min_idx = i;  
        for (int j = i + 1; j < len; j++) {  
            if (str[j] < str[min_idx] || (str[j] == str[min_idx] && islower(str[j]))) {  
                min_idx = j;  
            }  
        }  
        if (min_idx != i) {  
            char temp = str[i];  
            str[i] = str[min_idx];  
            str[min_idx] = temp;  
        }  
    }  
}